1. Field of the Invention
The present invention relates to network systems, and particularly to public network systems, such as the Internet. More particularly, the invention relates to a method and system for the caching of streaming multimedia data (e.g., audio and video data) from a content provider over a network to a client's computer.
2. Description of the Related Art
Computer networks such as the Internet are increasingly being used to transmit multimedia data (e.g., audio and video data). The enormous increase in traffic from transmitting such data has severely strained the Internet infrastructure. The data congestion problem is only expected to grow in the future as new multimedia data and new media rich Internet services such as e-commerce become widespread. Before the recent explosion of transmitting multimedia data over the Internet, data caching has become the preferred solution to address the problem of network congestion. Data caching attempts to move web content closer to the end-user and thus, minimize network and web server load, thereby improving the performance perceived by the end-user.
Data caching has been extensively implemented on the Internet to reduce network load (i.e., bandwidth consumption), server load, and response time. Existing data caching systems, typically cache entire web documents, such as HTML documents and images, for example, and attempt to keep the documents and images consistent with the origin server.
Current data caching systems are restrictive in that they only support static web clips such as HTML documents or images. Static web clips are typically small and as such are always cached in their entirety. Current caching methods do not adequately support streaming multimedia data, such as video and audio streaming media objects. Streaming multimedia data like video objects, for example, are usually too large to be cached in their entirety. With the recent proliferation of audio/video content on web sites, it is imperative that such data caches provide efficient support for streaming media. However, the aforementioned data caches treat multimedia (i.e., audio/video) clips as regular web objects, storing them in their entirety. Treating multimedia clips as regular web objects will prove to be adequate only in the short term as the size of multimedia clips on the web currently is relatively small. In the near future, however, faster Internet access technologies such as XDSL, DSL, VDSL and cable-modems will further enable the transmission of high-bandwidth, high resolution media clips that are much longer in duration than present day media clips. It will no longer be cost effective to cache such large media clips in their entirety.
The size of present day streaming media clips is typically at least an order of magnitude or two larger than that of a static web object, and therefore, do not lend themselves to be cached in their entirety. For example, a single, two hour long MPEG-2 movie requires about 4.5 GB of hard disk space. Given a fixed investment on buffer space, it is apparent that only a few media clips can be stored at a cache, and therefore, the hit ratio and the efficiency of the cache is limited. Given that caches have finite disk space, it is not feasible to statically store more than a few complete media clips. If there are several simultaneous requests for different media clips, it is easy to show that the cache will be busy replacing one media clip with another resulting in significant performance degradation.
One proposed solution to this problem is to break media clips into smaller segments and distribute those segments in a system of caches connected by a network. This approach has several disadvantages as described below. The approach has been extensively studied and employed in disk arrays such as “RAID: High performance, Reliable Secondary storage,” ACM Computing Surverys, June 1994, Chen, P., et al., and distributed cluster based video-on-demand servers, such as, Bolosky, W., et al., “The Tiger Video File-server,” Proceedings of NOSSDAV96, pp. 97–104, Zushi, Japan, Apr. 23–26, 1996, and Buddhikot, M., et al., “Design of a Large Scale Multimedia Storage Server,” Journal of Computer Networks and ISDN Systems, pp. 504–517, December 1994. Several research efforts such as Project MARS, Buddhikot, M., et al., “Design of a Large Scale Multimedia Storage Server,” Journal of Computer Networks and ISDN Systems, pp. 504–517, December 1994; Microsoft TIGER filesystem, Bolosky, W. et al., “The Tiger Video File-server,” Proceedings of NOSSDAV96, pp. 97–104, Zushi, Japan, Apr. 23–26, 1996; and Server Array, Bernhardt, C. et al., “The Server Array: A Scalable Video Server Architecture,” High-Speed Networks for Multimedia Applications, Academic Press, 1996, for example, have addressed the problems of distributed or striped layouts. However, their primary focus has been on video servers constructed using disks or tightly coupled clusters. Also, they focus on optimizing data layouts for high concurrency and balanced operation of clusters under normal playout and interactive playback operations such as fast-forward and rewind. They do not address configurations defining loosely coupled caching system as taught by the present invention.
FIG. 1 describes a basic model of a distributed cache including an origin server which stores thereon a plurality of multimedia clips. The origin server is connected to a plurality of streaming caches (SCs) in the network. Each SC services a plurality of multimedia-capable clients (MCs) in the network which request one or more of the multimedia clips.
With reference to a representative multimedia clip stored at the origin server, one prior art data layout approach, referred to herein as a simplistic approach, is to cache the multimedia clip in its entirety at each SC in the network. This data layout approach is problematic in that it is expensive to implement and not scalable with large numbers of clips. An alternative approach, referred to as a distributed data layout approach, is to break the multimedia clip into small segments of fixed or variable duration and distribute the segments among different SCs in the network thereby effectively constructing a distributed cache. In the distributed data layout approach, there are two models for constructing the distributed cache:
Origin Server Aware (OSA)—in this model, the origin server is aware of the SCs in the network and based on its knowledge of clip popularity (i.e., how often a clip is requested) decides how the clip should be distributed among all or a subset of the SCs. This approach is easier to implement across SCs supplied from different vendors as long as there is a standardized interface between the SCs and the origin server. However, it is often the case that the origin server is owned by a content provider and not by the ISP that operate the SCs. Therefore, it is not convenient to make the origin server aware of data distribution.
Origin Server Transparent (OST)—In this model, the origin server is unaware of how the clips are stored among the SCs which collectively define the distribution set. Data is distributed in small units the size of which can be unrelated to the actual data layout units. It is assumed that for every clip, each SC is aware of the number of SCs in the distribution set that stores the constituent segments of the clip. A simple state distribution protocol such as Internet Caching Protocol can be enhanced to exchange this information.
It is assumed that in both models the segments which comprise the multimedia clip are distributed to the SCs in the network in successive rounds where the number of rounds equals the number of segments in the clip. In each round, each segment of the clip is cached at one or more of the SCs in the network. When a client attempts to playback the clip, the client's designated SC provides information to the client regarding each SC that stores one or more segments of the clip. Playback software resident at the client then forms a playback schedule consisting of a list of SCs that need to be visited to playback the clip. Thus, the collection of SCs which defined the distribution set act as a single loosely coupled streaming cache.
Three performance metrics are now defined in the context of the OSA and OST models, discussed above, to assess the relative merits of the prior art data layout (i.e., distribution) schemes and the data layout scheme of the present invention.
Metric 1—Storage—It is assumed that each media clip stored at the origin server is of length L and it is further assumed that there are K streaming caches (i.e., SCs) in the network. In the simple storage scenario, discussed above, in which each SC caches the entire media clip, a total storage requirement for each clip would equal {L * K}. For the distributed data layout approach, discussed above, which stripes the segmented clips on K caches, a smaller amount of storage is required and in addition, this approach supports a larger number of concurrent requests.
Metric 2—Playback start-up latency—The playback start-up latency is an important metric for streaming caches and servers, and is defined as the time it takes for the stream playback to start from the time the client request is issued. When a clip is stored in its entirety at the closest cache in the simple storage scenario, the start-up latency is minimal. It is desirable that a distributed data layout preserves this property.
Metric 3—Number of switch-overs—When a client receives stream data from an SC, the stream is switched to successive SCs in the distribution set as the playback progresses. Such switch-overs have an associated cost in the form of latency for signaling and buffering the data from latter SCs in sequence and can result in a potential break in the playout. It is desirable to limit the number of such switch-overs in a distributed data layout.
A primary goal for designing a data layout scheme is to balance the trade-offs between the three parameters discussed above. A need exists for a system and method for enhancing current caching systems to support streaming multimedia distributed over a loosely coupled caching system which balances the trade-offs between the three parameters discussed above.